It is sometimes required to update content stored in a storage device. For example, if the content is software (such as an executable file), it is sometimes required to fix a bug in it or to update it thus generating a newer version. Hereinafter the term “old version” or “original version” refers to content before update, the term “new version”, or “updated version” refers to the content after it was updated, the term “update process” refers to the process that performs the update of the storage content and the term “update package” or “delta file” refers to the data which is used by the update process in addition to the old version.
There are several ways known in the art for generating update packages and using them for updating versions. For example, U.S. Pat. No. 6,546,552 (“Difference extraction between two versions of data-tables containing intra-references”, published 2003) discloses a method for generating a compact difference result between an old program and a new program. Each program includes reference entries that contain references that refer to other entries in the program. According to the method of U.S. Pat. No. 6,546,552, the old program is scanned and for each reference entry, the reference is replaced by a distinct label mark, whereby a modified old program is generated. In addition, according to U.S. Pat. No. 6,546,552, the new program is scanned and for each reference entry the reference is replaced by a distinct label mark, whereby a modified new program is generated. Thus, utilizing directly or indirectly the modified old program and modified new program, the difference result is generated.
WO 2004/114130 (“Method and system for updating versions of content stored in a storage device”, published 2004) discloses a system and method for generating a compact update package between an old version of content and a new version of content. The system of WO 2004/114130 includes a conversion element generator for generating a conversion element associated with the old version and new version. It also includes a modified version generator for generating a modified version, and an update package generator for generating the compact update package. The compact update package includes the conversion element and a modified delta based on the modified version and the new version.
WO 2005/003963 (“Method and system for updating versions of content stored in a storage device”, published 2005) discloses a system and method for updating versions of content stored in a storage device. The system of WO 2005/003963 includes an update module for obtaining a conversion element and a small delta. It also includes a converted old items generator for generating converted old items by applying the conversion element to items of an old version, a data entries generator for generating data entries based on the modified data entries and on the converted old item, and a new version generator for generating a new version of content by applying the commands and the data entries to the old version.
U.S. Pat. No. 6,832,373 (“System and method for updating and distributing information”, published 2004) discloses devices, systems and methods for updating digital information sequences that are comprised by software, devices, and data. In addition, these digital information sequences may be stored and used in various forms, including, but not limited to files, memory locations, and/or embedded storage locations. Furthermore, the devices, systems, and methods described in U.S. Pat. No. 6,832,373 provide a developer skilled in the art with an ability to generate update information as needed and, additionally, allow users to proceed through a simplified update path, which is not error-prone, and may be performed more quickly than through the use of technologies existing when U.S. Pat. No. 6,832,373 was filed.
It can be appreciated that sometimes, two versions of the same content contain common parts which appear both in the old and the new versions. It can be also appreciated that the position of these common parts need not necessarily be the same in both versions and that they can change their position. Update methods known in the art such as delta-update methods take advantage of the common parts, and use update packages that contain instructions for copying the common parts as well as other changes that together enable the update process to create a the desired new version.
It is known to persons versed in the art that content is stored in a storage device, such as disk or memory. Also, sometimes the new version can use the same storage area previously occupying the old version. For example, if the available storage in the device is limited in space, it can be preferred to store the new version in place of the old version, saving space thereby. Such an update process, where the new version occupies at least some of the space previously occupied by the old version, is referred in the art as “in-place update” or “updating in-place”.
One of the outcomes of this method is that once a storage area has been updated, its previous content being part of the old version is lost. When performing an in-place update, one has to take care of the reliability of the update process and enable it to properly resume after an unexpected interrupt such as power failure. Methods to handle the reliability of such process are known in the art. The prior art shows how to insure the reliability of an in-place update process by using state-memory and backup buffer; Since interruptions may leave some memory area corrupted, an in-place update process can back-up any content intended to be written on a specially designated backup buffer, creating a copy of the content thereby, and only upon successful creation of the copy, the area of the storage to be updated is being modified. This technique is sometimes referred in the art as ‘2-phase committing’. Another requirement of the reliability of such update process is to keep state information indicative of progress of the update process properly saved in a storage device so that a resuming update process will be able to restore its condition as what was exactly before the interruption and be able to continue properly as if the interruption never occurred. This requirement is achieved by the prior art by recording every successful update step in a non-volatile storage area in such way that a resuming update process can read and use it in order to start with a state substantially similar to the state of the update interrupted process.
Those versed in the art will appreciate that many storage devices include identified areas in them. For example, hard drives include sectors and so do flash memory modules. An identified area in a storage device is referred to as a “storage block”. It is noted though that hard drives and flash memory modules are only two examples of a storage device. There are other known per se storage devices such as Random Access Memory (RAM) etc. It should be further noted that the term “block” or “region” is used hereinafter to refer to an identified area in the content of one or both versions.
A known problem in the art occurs when blocks in the new version which are matched to corresponding blocks in the old version, change position and sometimes change also their order during in-place update, where the storage of the new version occupies at least part of the same storage area as of the old version.
There are methods known in the art for performing in-place update, amongst which are those methods generally known as “delta-update”, or “update package update”, wherein an update process operates in accordance with an update package or a delta file. Basically, in accordance with those methods, areas in the storage which do not change their content except for their position, are being copied and moved to their position in the new version instead of generating them from new. Specifically, when performing an in-place update, blocks' copying must be performed with care since the target location of these blocks may contain data still necessary to the update process for operations performed after the copy. This problem is known in the art sometimes as ‘collisions’ or ‘write-before-read conflicts’, hereinafter called ‘conflicts’. In some cases, conflicts can be simply avoided by determining the correct order of the copying the blocks, hereinafter called ‘copy-order’. Resolving conflicts starts by copying a block to a place that does not accommodate data that is still needed for future operations, and freeing at the area occupied by that block before it was copied (i.e., the corresponding block in the old version) and continues by copying blocks only to places that are free, until no more blocks can be copied into free places.
It should be noted, that sometimes, these series of copy operations may form a cycle, where a block's new position overlaps another block's old position whose new position overlaps another's old position and so on until the a block with a new position that overlaps the first block's old position. Hereinafter these cycles are referred as ‘copy-cycles’. It is know in the art that such copy-cycles creates groups of conflicts for which there is no copy-order by which all the group's conflicts will be resolved and at least one will remain unresolved.
U.S. Pat. No. 6,018,747 (“Method for generating and reconstructing in-place delta files”, published 2000) discloses a method, apparatus, and article of manufacture for generating, transmitting, replicating, and rebuilding in-place reconstructible software updates to a file from a source computer to a target. U.S. Pat. No. 6,018,747 stores the first version of the file and the updates to the first version of the file in the memory of the source computer. The first version is also stored in the memory of the target computer. The updates are then transmitted from the memory of the source computer to the memory of the target computer. These updates are used at the target computer to build the second version of the file in-place.
According to U.S. Pat. No. 6,018,747, when a delta file attempts to read from a memory offset that has already been written, this will result in an incorrect reconstruction since the prior version data has been overwritten. This is termed a write before read conflict. U.S. Pat. No. 6,018,747 teaches how to post-process a delta file in order to create a delta file minimize the number of write before read conflicts and then replace copy commands with add commands to eliminate conflicts. A digraph is generated, for representing the write before read conflicts between copy commands. A schedule is generated that eliminates write before read conflicts by converting this digraph into an acyclic digraph.
There is a need in the art, thus, for an efficient and fast in-place update mechanism.